// https://leetcode.cn/problems/optimal-division/description/

// 算法思路总结：
// 1. 数学优化：除法连除时添加括号使结果最大化
// 2. 固定模式：第一个数除以后面所有数的连除结果
// 3. 在第一个除法后添加括号包含后续所有数
// 4. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <string>
#include <vector>
#include <algorithm>

class Solution 
{
public:
    string optimalDivision(vector<int>& nums) 
    {
        int m = nums.size();
        if (m == 1) return to_string(nums[0]);
        if (m == 2) return to_string(nums[0]) + "/" + to_string(nums[1]);
        
        string res;
        for (int i = 0 ; i < m ; i++)
        {   
            res += to_string(nums[i]);
            if (i != m - 1)
                res += '/';
            if (i == 0)
                res += '(';
            if (i == m - 1)
                res += ')';
        }

        return res;
    }
};

int main()
{
    vector<int> v1 = {1000,100,10,2}, v2 = {2,3,4};
    Solution sol;

    cout << sol.optimalDivision(v1) << endl;
    cout << sol.optimalDivision(v2) << endl;

    return 0;
}